class Solution:
    def maximumXorProduct(self, a: int, b: int, n: int) -> int:
        mod = 1000000007
        if n == 0:
            return a * b % mod
        if a < b:
            a, b = b, a
        x = a - (a & ((1 << n) - 1))
        y = b - (b & ((1 << n) - 1))
        f = x > y
        limit = 1 << (n - 1)
        while limit > 0:
            if a & limit == b & limit:
                x |= limit
                y |= limit
            else:
                if f:
                    y |= limit
                else:
                    x |= limit
                    f = True
            limit >>= 1
        return x * y % mod


s = Solution()
print(s.maximumXorProduct(a=0, b=3, n=1) == 2)
k = 1 << 5
print(bin(k))
print(bin(k - 1))
print(bin(~(k - 1)))

12
5
4
6
7
5
1
6
3
0
3
1
0
4
0
0
6
1
648899250667091
408304371447992
0
